package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/sqrtx/description/'>x的平方根Sqrt(x)</a>
 * <p>给你一个非负整数 x ，计算并返回 x 的 算术平方根 。</p>
 * <p>由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。</p>
 * <p>注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。</p>
 *
 * <p>
 * <pre>
 *         示例 1：
 *              输入：x = 4
 *              输出：2
 *
 *          示例 2：
 *              输入：x = 8
 *              输出：2
 *              解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *     </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>0 <= x <= 2^31 - 1</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2022/5/26 9:00
 */
public class LC0069mySqrt {

    static class Solution {
        /**
         * 求开方(二分查找)
         *
         * @param x 整数x     0 <= x <= 2^31 -1
         */
        public int mySqrt(int x) {
            int ans = -1;
            int left = 1;
            int right = x;
            while (left <= right) {
                // 平均数
                int mid = left + ((right - left) >> 1);
                // 平均数的平方
                long value = (long) mid * mid;
                if (value == x) {
                    return mid;
                } else if (value > x) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return ans;
        }
    }
}
